// greedy alg.
// 通过局部最优解得到全局最优解
// 目的地倒推法：初始目的地为lastlast，先计算最后一步，再计算倒数第二步，直到初始位置0.
// i + nums[i] >= len(nums) - 1
// time:最坏O(n^2), space: O(1)
func jump(nums []int) int {
	dest := len(nums) - 1
	steps := 0
	for dest > 0 {
		// exclude dest
		for i := 0; i < dest; i++ {
			if i+nums[i] >= dest {
				dest = i
				steps++
				break
			}
		}
	}
	return steps
}